package com.base.graph;

import java.util.*;

/**
 * @ClassName: CountPaths
 * @Description: 5836. 到达目的地的方案数
 * <p>
 * 你在一个城市里，城市由 n个路口组成，路口编号为0到n - 1，某些路口之间有 双向道路。输入保证你可以从任意路口出发到达其他任意路口，且任意两个路口之间最多有一条路。
 * <p>
 * 给你一个整数n和二维整数数组roads，其中roads[i] = [ui, vi, timei]表示在路口ui和vi之间有一条需要花费timei时间才能通过的道路。你想知道花费 最少时间从路口0出发到达路口n - 1的方案数。
 * <p>
 * 请返回花费 最少时间到达目的地的 路径数目。由于答案可能很大，将结果对109 + 7取余后返回
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/number-of-ways-to-arrive-at-destination
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author: li
 * @Date: 2021/8/23 6:56 下午
 */
public class CountPaths {
    /**
     * @param n 结点数
     * @param roads 无向图
     * @return 最小路径数
     *
     */
    final long INF = Long.MAX_VALUE >> 1;
    final int MOD = 1000000007;

    public int countPaths(int n, int[][] roads) {
        long[][] graph = new long[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(graph[i], INF);
        }
        for (int[] road : roads) {
            graph[road[0]][road[1]] = road[2];
            graph[road[1]][road[0]] = road[2];
        }
        // dp[0][i] 记录从 0 到每一个点的最短距离
        // dp[1][i] 记录从 0 到每一个点的最短路径的数量
        long[][] dp = new long[2][n];
        Arrays.fill(dp[0], INF);
        dp[0][0] = 0;
        dp[1][0] = 1;
        // 小根堆PriorityQueue用来找距离 0 最近的节点
        // 堆中数组对象 [0] 是距离， [1] 是节点 id
        PriorityQueue<long[]> minHeap = new PriorityQueue<>(Comparator.comparingLong(o -> o[0]));
        minHeap.add(new long[]{0L, 0L});
        while (!minHeap.isEmpty()) {
            // 取出距离 0 最近的节点
            long[] p = minHeap.poll();
            long dist = p[0];
            int i = (int) p[1];
            // 如果从 0 到 i 的距离大于或等于 dist，则更新 dist 数组
            if (dp[0][i] >= dist) {
                for (int j = 0; j < n; j++) {
                    long newDist = dp[0][i] + (long) graph[i][j];
                    // 如果新路径的长度没变，那么将经过 i 到达 j 的路径数量计入
                    if (newDist == dp[0][j]) {
                        dp[1][j] = (dp[1][i] + dp[1][j]) % MOD;
                    }
                    // 如果出现了新的更短的路径，记录之并将最短路径的数量置为 dp[1][i]
                    if (newDist < dp[0][j]) {
                        dp[0][j] = newDist;
                        minHeap.add(new long[]{newDist, j});
                        dp[1][j] = dp[1][i];
                    }
                }
            }
        }
        return (int) dp[1][n - 1];
    }

//
//    作者：kevin_hwang
//    链接：https://leetcode-cn.com/problems/number-of-ways-to-arrive-at-destination/solution/java-dijkstrabian-chong-by-kevin_hwang-gi73/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}
